package datastructure.priorityqueue;

/**
 * 基于无序数组实现优先队列
 *
 * @author 杨 强
 * @package datastructure.priorityqueue
 * @createTime 2023-03-16 21:50
 */
public class NoOrderArrayPriorityQueue<E extends Priority> implements Queue<E> {
    public static void main(String[] args) {
        Element element1 = new Element(1, 1);
        Element element2 = new Element(2, 2);
        Element element3 = new Element(3, 3);

        NoOrderArrayPriorityQueue<Element> queue = new NoOrderArrayPriorityQueue(5);

        queue.offer(element1);
        queue.offer(element2);
        queue.offer(element3);

        System.out.println(queue.poll().data);
    }

    /**
     * 储存元素的数组
     */
    Priority[] array;
    /**
     * 队列元素的个数
     */
    private int size;

    /**
     * 构造器初始化底层储存数据的数组的容量
     * @param capacity 容量
     */
    public NoOrderArrayPriorityQueue(int capacity) {
        array = new Priority[capacity];
    }

    /**
     * 删除元素的方法
     * @param index 需要删除元素的下标值
     */
    private void remove(int index) {
        if (index < size - 1) {
            System.arraycopy(array, index + 1,
                    array, index, size - 1 - index);
        }
        array[--size] = null; // help GC
    }

    /**
     * 计算最大优先级下标元素的方法
     * @return
     */
    private int selectMax() {
        // 从0坐标开始找
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (array[i].priority() > array[max].priority()) {
                max = i;
            }
        }
        return max;
    }

    @Override
    public boolean offer(E value) {
        // 判断满
        if (isFull()){
            return false;
        }
        // 直接添加到最后一个下标
        array[size] = value;
        size++;
        return true;
    }

    @Override
    public E poll() {
        // 判断空
        if (isEmpty()){
           return null;
        }
        // 找到最大值下标
        int maxIndex = selectMax();
        Priority priority = array[maxIndex];
        // 移除
        remove(maxIndex);
        return (E)priority;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        // 得到最大值的下标
        int max = selectMax();
        // 直接返回
        return (E) array[max];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
